/**
 * 数组异或和定义如下：
 * 相邻两个元素异或，如此得到一个新的数组，且长度比原来少1
 * 反复这个过程，直到只剩一个数，这个数就称为数组的异或和
 * 给定一个数组，和若干个询问，对每个询问[s, e]:
 * 求 A[s...e] 子数组最大的异或和
 * 
 * 找规律，发现D[s][e] = D[s][e - 1] ^ D[s + 1][e]
 * 因此可以在O(N^2)时间内算出所有子数组异或和
 * N在2000
 * 
 * 再令Z[s][e]记作A[s...e]之间的最大异或和，则只有三种可能：
 * Z[s][e] = max(D[s][e], Z[s + 1][e], Z[s][e - 1])
 * 同样在 O(N^2) 可以求出
 */
class Solution {

vector<vector<int>> D;
vector<vector<int>> Z;
int N;

public:
    vector<int> maximumSubarrayXor(vector<int>& nums, vector<vector<int>>& queries) {
        N = nums.size();
        D.assign(N, vector<int>(N, -1));    
        Z.assign(N, vector<int>(N, -1)); 

        for(int i=0;i<N;++i) D[i][i] = Z[i][i] = nums[i];

        vector<int> ans;
        for(const auto & vec: queries){
            auto a = vec[0];
            auto b = vec[1];
            ans.emplace_back(proc(a, b));
        }

        return ans;
    }

    int proc(int a, int b){
        if(-1 != Z[a][b]) return Z[a][b];

        return Z[a][b] = max(dp(a, b), max(proc(a, b - 1), proc(a + 1, b)));
    }

    int dp(int a, int b) {
        if(-1 != D[a][b]) return D[a][b];
        return D[a][b] = dp(a + 1, b) ^ dp(a, b - 1);
    }


};

